package two.chapter_2.c2_4;

import java.util.Iterator;

/**
 * 使用二叉堆数据结构
 *
 * @param <Item>
 */
public class MaxPriorityQueue<Item extends Comparable<Item>> extends AbstractMaxPriorityQueue<Item> {
    //数组items[0]不用，从items[1]开始到items[size]
    private Item[] items;

    public MaxPriorityQueue(int max) {
        items = (Item[]) new Comparable[max + 1];
    }

    /**
     * 返回最大元素
     *
     * @return
     */
    public Item max() {
        return (Item) items[1];
    }

    /**
     * 删除并返回最大元素
     *步骤：
     *    1，从第一个元素中获取最大元素
     *    2，交换第一个和最后一个元素位置
     *    3，元素总数减1
     *    4，第一个元素做下沉操作。
     * @return
     */
    public Item delMax() {
        Item max = (Item) items[1];
        exch(1, size--);//将第一个元素和最后一个元素交换位置
        items[size + 1] = null;
        sink(1);
        return max;
    }

    /**
     * 插入操作
     *    1，先插入到数组最后面，
     *    2，元素总数加1
     *    3，然后再执行上浮操作
     *
     * @param item
     */
    @Override
    public void insert(Item item) {
        items[++size]=item;
        swim(size);
    }


    @Override
    public Iterator<Item> iterator() {
        return null;
    }

    /**
     * 上浮操作
     *
     * @param k
     */
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k/2,k);
            k = k / 2;
        }
    }

    /**
     * 下沉操作
     * @param k
     */
    private void sink(int k) {
        while (2 * k <= k) {
            int j = 2 * k;
            if (j < size && less(j, j + 1)) j++;

            if (!less(k, j)) break;

            exch(k, j);
            k = j;
        }
       /* while (k<size){
            if (less(2*k,2*k+1)){
                exch(2*k+1,k);
                k=2*k+1;
            }else {
                exch(2*k,k);
                k=2*k;
            }

        }*/
    }

    private void exch(int i, int j) {
        Item temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }
}
